#include<Stdio.h>
#include<stdlib.h>

 typedef struct ListNode
 {
   int val;
   struct ListNode* next; 
}SLTNode;

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;

    while (cur)
    {
        if (cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        else
        {
            if (prev == NULL)
            {
                head = head->next;
                free(cur);
                cur = head;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }

        }
    }

    return head;

}

void test01()
{
    SLTNode* n1 = (SLTNode*)malloc(sizeof(struct ListNode));
    SLTNode* n2 = (SLTNode*)malloc(sizeof(struct ListNode));
    SLTNode* n3 = (SLTNode*)malloc(sizeof(struct ListNode));
    SLTNode* n4 = (SLTNode*)malloc(sizeof(struct ListNode));

    n1->val = 7;
    n2->val = 7;
    n3->val = 7;
    n4->val = 7;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = NULL;

    SLTNode* ret = removeElements(n1, 7);
    SLTNode* cur = ret;
    while (cur)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("NULL\n");


}


struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    struct ListNode* tail = NULL;


    while (cur)
    {
        if (cur->val != val)
        {
            if (newhead == NULL)
            {
                newhead = cur;
                tail = cur;
                cur = cur->next;
            }
            else
            {
                tail->next = cur;
                cur = cur->next;
                tail = tail->next;
            }
        }
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }

    if (tail)
        tail->next = NULL;


    return newhead;
}

void test02()
{
    SLTNode* n1 = (SLTNode*)malloc(sizeof(struct ListNode));
    SLTNode* n2 = (SLTNode*)malloc(sizeof(struct ListNode));
    SLTNode* n3 = (SLTNode*)malloc(sizeof(struct ListNode));
    SLTNode* n4 = (SLTNode*)malloc(sizeof(struct ListNode));

    n1->val = 7;
    n2->val = 7;
    n3->val = 7;
    n4->val = 7;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = NULL;

    SLTNode* ret = removeElements(n1, 7);
    SLTNode* cur = ret;
    while (cur)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("NULL\n");

}



struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {

    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;

    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));

    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }

    if (list1)
        tail->next = list1;
    if (list2)
        tail->next = list2;

    struct ListNode* first = head->next;
    free(head);
    return first;
}


struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;

    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }

    return newhead;
}


int main()
{
    //test01();
    test02();
    return 0;
}


